47. 全排列II

发表于 | 分类于 | 阅读次数：

链接：https://leetcode-cn.com/problems/permutations-ii/

题目描述

给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例:

1
2
3
4
5
6
7
输入: [1,1,2]
输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

题目分析

本题简单的回溯法即可解决。和之前的回溯法都区别不大，唯一的区别是，本题中要求的是非重复的，所以需要记一下已经访问的序列。

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
    def __init__(self):
        self.result_all = None
        self.visited = None
    
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        self.result_all = []
        self.visited = [0 for _ in range(len(nums))]
        nums = sorted(nums)
        self.dfs(nums, 0, [])
        return self.result_all
    
    def dfs(self, nums, n, result):
        if n == len(nums):
            self.result_all.append(result[:])
            return
        
        pre_num = []
        for i in range(len(nums)):
            if self.visited[i] == 1:
                continue
            if nums[i] in pre_num:
                continue
            pre_num.append(nums[i])
            result.append(nums[i])
            self.visited[i] = 1
            self.dfs(nums, n + 1, result)
            result.pop()
            self.visited[i] = 0
        return